User-Guided Program Reasoning using Bayesian Inference

1. User-Guided Program Reasoning using Bayesian Inference

User-Guided Program Reasoning using Bayesian Inference

这篇文章和《ProbLog: A Probabilistic Prolog and its Application in Link Discovery》有些相似小。在Problog一文中，加上了概率值的是Datalog中的一条条规则，通过BDD来解决概率计算。而在本文中，是将Datalog的对应的派生图视作贝叶斯网络来解决的，同样也需要将规则加上概率值。

https://zh.wikipedia.org/wiki/%E8%B2%9D%E6%B0%8F%E7%B6%B2%E8%B7%AF#

这篇文章最主要的算法就是这个：

详细解释一下：

• 第一步是输入待分析的程序，输出程序中的所有关系。
• 第二步是将输入进Datalog程序中，得到IDB 。通过加上原有的EDB 可以得到派生图。是经Datalog运算得到的警报信息。
• 第三步要消除派生图中的环，因为派生图要转成贝叶斯网络，而贝叶斯网络是有向无环图。
• 第四步做了一些优化。
• 第五步构建贝叶斯网络。构造过程需要用到派生图和各个规则的触发概率。
• 第六步初始化用户反馈集为空集。
• 第七步开始运用用户反馈，通过用户反馈根据贝叶斯网络计算条件概率并排序，每次选取排序最高的向用户寻求反馈，再据此迭代。

上面这套流程中有个东西没有讲是怎么来的，就是这个各个规则的触发概率​。对于完全标记数据的语料库，规则概率只是规则在给定真实假设的情况下产生错误结论的次数除以总次数得到的值。对于标记较少的数据集，一个面临潜在（或未观察到）变量的挑战，可以用下面描述的期望最大化（EM）算法来解决。

假设我们有一个数据集，这个数据集标注了各个需要警报的地方的真实结果（即需要警报的地方实际上要不要警报）。现在我们要拿这个去推算规则的概率。根据EM算法的过程，首先随机初始化各规则的概率，然后根据派生图导出的贝叶斯网络得到，即报警的概率。然后利用下面的公式进行更新：

其中代表是与规则有关的地方。为真实结果，若为0的话整个也就为0。

经过一轮轮迭代最终达到稳定就是各个规则的触发概率了。

但是，这篇文章最神奇的地方我觉得也在这里，讲EM算法时来了这么一段：

这个的意思是他在实验中根本没用EM算法，而是直接把概率定成0.999了吗😥